package cn.rocky.prepare;

import java.util.HashMap;
import java.util.Map;

/**
 * 6168. 恰好移动 k 步到达某一位置的方法数目
 */
public class numberOfWays {

    int s, e, MOD =(int) 1e9 + 7;
    Map<Integer, Long> map = new HashMap<>();
    public int numberOfWays(int startPos, int endPos, int k) {
        s = startPos; e = endPos;
        return (int)dfs(s, k);
    }
    long dfs(int idx, int rest) {
        if (Math.abs(idx - e) > rest) return 0; // 剪枝
        if (rest == 0) return 1;                // 此时rest = 0, 并且因为上一个 if 的过滤,所以idx肯定到达了终点
        int key = idx * 1000 + rest;
        if (map.containsKey(key)) {
            return map.get(key);
        }
        long value = (dfs(idx + 1,rest - 1) + dfs(idx - 1,rest - 1)) % MOD;
        map.put(key, value);
        return value;
    }


    public static int numberOfWays1(int startPos, int endPos, int k) {
        if (endPos - startPos > k) {return 0;}
        int step = endPos - startPos + 1;
        if (checkNumber(step, k)) {return 0;}
        // 求总共有多少种步法
        return 0;
    }

    public static boolean checkNumber(int step, int k) {
        if (k % step == 0 || k % step == 2) {return false;}
        return true;
    }

    public static void main(String[] args) {
        int startPos = 2;
        int endPos = 4;
        int step = endPos - startPos + 1;
        int k = 8;
    }
}
